home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 5 / Amiga Tools 5.iso / tools / developer-tools / andere sprachen / oberonv4 / demos / sortplus.mod (.txt) < prev    next >
Encoding:
Oberon Text  |  1996-02-01  |  2.3 KB  |  99 lines
  1. Syntax10.Scn.Fnt
  2. Syntax10b.Scn.Fnt
  3. MODULE SortPlus;
  4. IMPORT S:=SortBasics;
  5. CONST N=150;
  6. PROCEDURE InsertSort;
  7.     VAR i, k, x, y: INTEGER;
  8.     BEGIN
  9.         FOR i:=1 TO N-1 DO
  10.             S.Get(i, x); k:=i-1;
  11.             LOOP
  12.                 S.Get(k, y); IF x >= y THEN EXIT END;
  13.                 S.Put(k+1, y);
  14.                 DEC(k); IF k=-1 THEN EXIT END
  15.             END;
  16.             S.Put(k+1, x)
  17.         END;
  18.         S.Done;
  19.     END InsertSort;
  20. PROCEDURE Insert*;
  21.     BEGIN S.Install(InsertSort, N, "Insert") END Insert;
  22. PROCEDURE BubbleSort;
  23.         i, x, y: INTEGER;
  24.         sorted: BOOLEAN;
  25.     BEGIN
  26.         REPEAT
  27.             sorted:=TRUE;
  28.             FOR i:=1 TO N-1 DO
  29.                 S.Get(i-1, x); S.Get(i, y);
  30.                 IF x>y THEN S.Put(i-1, y); S.Put(i, x); sorted:=FALSE END
  31.             END
  32.         UNTIL sorted;
  33.         S.Done;
  34.     END BubbleSort;
  35. PROCEDURE Bubble*;
  36.     BEGIN S.Install(BubbleSort, N, "Bubble") END Bubble;
  37. PROCEDURE HeapSort;
  38.     VAR l, r, elemL, elemR: INTEGER;
  39.     PROCEDURE Sift;
  40.         VAR l1, r1, x: INTEGER;
  41.         BEGIN
  42.             l1:=l; S.Get(l1, elemL);
  43.             LOOP
  44.                 r1:=2*l1; IF r1 > r THEN EXIT END;
  45.                 S.Get(r1, elemR);
  46.                 IF r1 < r THEN
  47.                     S.Get(r1+1, x); IF elemR < x THEN elemR:=x; INC(r1) END;
  48.                 END;
  49.                 IF elemL >= elemR THEN EXIT END;
  50.                 S.Put(l1, elemR); l1:=r1
  51.             END;
  52.             S.Put(l1, elemL)
  53.         END Sift;
  54.     BEGIN
  55.         l:=N DIV 2; r:=N-1;
  56.         WHILE l>0 DO DEC(l); Sift END;
  57.         WHILE r>0 DO
  58.             S.Get(l, elemL); S.Get(r, elemR); S.Put(l, elemR); S.Put(r, elemL);
  59.             DEC(r); Sift
  60.         END;
  61.         S.Done;
  62.     END HeapSort;
  63. PROCEDURE Heap*;
  64.     BEGIN S.Install(HeapSort, N, "Heap") END Heap;
  65. PROCEDURE QuickSort;
  66.     PROCEDURE Q(l, r: INTEGER);
  67.         VAR key, l1, r1, elemL, elemR: INTEGER;
  68.         BEGIN
  69.             S.Get(l, key);
  70.             l1:=l; r1:=r;
  71.             REPEAT
  72.                 LOOP S.Get(l1, elemL); IF elemL >= key THEN EXIT END; INC(l1) END;
  73.                 LOOP S.Get(r1, elemR); IF elemR <= key THEN EXIT END; DEC(r1) END;
  74.                 IF l1 <= r1 THEN
  75.                     S.Put(l1, elemR); S.Put(r1, elemL);
  76.                     INC(l1); DEC(r1)
  77.                 END
  78.             UNTIL l1 > r1;
  79.             IF l < r1 THEN Q(l, r1) END;
  80.             IF l1 < r THEN Q(l1, r) END
  81.         END Q;
  82.     BEGIN
  83.         Q(0, N-1);
  84.         S.Done
  85.     END QuickSort;
  86. PROCEDURE Quick*;
  87.     BEGIN S.Install(QuickSort, N, "Quick") END Quick;
  88. PROCEDURE Start*;
  89.     BEGIN S.Schedule END Start;
  90. PROCEDURE Randomize*;
  91.         i, r: INTEGER;
  92.         data: S.Data;
  93.     BEGIN
  94.         data[0]:=0;
  95.         FOR i:=1 TO N-1 DO r:=S.RND(i+1); data[i]:=data[r]; data[r]:=i END;
  96.         S.NewData(data, N)
  97.     END Randomize;
  98. END SortPlus.
  99.